package com.algorithm.btree;

import java.util.List;

import junit.framework.Assert;

import org.junit.Before;
import org.junit.Test;

public class TestBTree {
	BTree<Integer, Integer> tree;
	int count = 1000;

	@Before
	public void setUp() throws Exception {
		tree = new BTree<Integer, Integer>(4, false);
		for (int i = 1; i < count; i++) {
			tree.insert(i, i * i);
		}
	}

	@Test
	public void testInsert() {
		for (int i = 1; i < count; i++) {
			Assert.assertEquals(i * i, (int) tree.find(i));
		}
	}

	@Test
	public void testDelete() {
		for (int i = 1; i < count; i++) {
			tree.delete(i);
		}
		for (int i = 1; i < count; i++) {
			Assert.assertEquals(null, tree.find(i));
		}
	}

	@Test
	public void testUpdate() {
		for (int i = 1; i < count; i++) {
			tree.updateValue(i, i + 1);
		}
		for (int i = 1; i < count; i++) {
			Assert.assertEquals(i + 1, (int) tree.find(i));
		}
	}

	@Test
	public void testFindRange() {
		tree = new BTree<Integer, Integer>(4, false);
		for (int i = 1; i <= 100; i++) {
			tree.insert(i, i);
		}
		List<Integer> result = tree.findAll(50, 10000, 4, 10);
		Assert.assertEquals(10, result.size());
		for (int i = 0; i < result.size(); i++) {
			Assert.assertEquals(50 + 4 + i, (int) result.get(i));
		}

		result = tree.findAll(99, 10000, 0, 10);
		Assert.assertEquals(2, result.size());
		for (int i = 0; i < result.size(); i++) {
			Assert.assertEquals(99 + i, (int) result.get(i));
		}
	}

	@Test
	public void testDeleteRange() {
		tree = new BTree<Integer, Integer>(4);
		for (int i = 1; i <= 20; i++) {
			tree.insert(i, i);
		}
		tree.delete(10, 19);
		List<Integer> result = tree.findAll(0, 10000, 0, 100);
		Assert.assertEquals(10, result.size());

	}

	@Test
	public void testInsertDupKey() {
		tree = new BTree<Integer, Integer>(4);
		for (int i = 1; i <= 100; i++) {
			tree.insert(i % 10, i % 10);
		}

		for (int i = 1; i <= 100; i++) {
			Assert.assertEquals(i % 10, (int) tree.find(i % 10));
		}
	}

	@Test
	public void testDeleteDupKey() {
		int count = 100;
		tree = new BTree<Integer, Integer>(4);
		for (int i = 1; i <= count; i++) {
			tree.insert(i % 10, i % 10);
		}
		// System.out.println(tree);
		for (int i = 0; i < 10; i++) {
			tree.delete(i % 10);
			// System.out.println(tree);
		}

		for (int i = 1; i <= 100; i++) {
			Assert.assertEquals(null, tree.find(i % 10));
		}
	}

}
